import defaultHashCode from "./hash_code";
import { isPrime } from "./is_prime";

const MAX_LOAD_FACTOR = 0.75;
const MIN_LOAD_FACTOR = 0.25;

class HashTable {
  constructor(hashCode = defaultHashCode) {
    this.hashCode = hashCode;
    this.items = []; // 哈希表存储的数据
    this.count = 0; // 哈希表存储的数据的数量
    this.limit = 7; // 哈希表的容量
  }

  // 插入
  // 哈希表的插入和修改操作是同一个函数：因为，当使用者传入一个 [key, value] 时，如果原来不存在该 key，那么就是插入操作，如果原来已经存在该 key，那么就是修改操作
  put(key, value) {
    // 1. 把 key 哈希化
    const hashKey = this.hashCode(key, this.limit);

    // 2. 判断 this.items[hashKey]是否已经存在
    let item = this.items[hashKey];
    if (item === undefined) {
      item = [];
      this.items[hashKey] = item;
    }

    // 3. 判断是不是修改数据
    for (let i = 0; i < item.length; i++) {
      const unit = item[i];
      const k = unit[0];
      if (key === k) {
        console.log("修改");
        unit[1] = value;
        return;
      }
    }

    // 4. 插入数据
    this.items[hashKey].push([key, value]);
    this.count++;

    // 5. 判断是否需要扩容
    const loadFactor = this.count / this.limit;
    if (loadFactor > MAX_LOAD_FACTOR) {
      this.resize(this.getPrime(this.limit * 2));
    }
    return;
  }

  // 查找数据
  get(key) {
    // 1. 把 key 哈希化
    const hashKey = this.hashCode(key, this.limit);
    // 2. 判断 this.items[hashKey]是否存在
    let item = this.items[hashKey];
    // 2.1 不存在说明找不到
    if (item === undefined) {
      return false;
    }
    // 2.2 存在则遍历item，找出对应的value
    for (let i = 0; i < item.length; i++) {
      const unit = item[i];
      const k = unit[0];
      const v = unit[1];
      if (key === k) {
        return v;
      }
    }
    return false;
  }

  // 删除
  remove(key) {
    // 1. 把 key 哈希化
    const hashKey = this.hashCode(key, this.limit);
    // 2. 判断 this.items[hashKey]是否存在
    let item = this.items[hashKey];
    // 2.1 不存在说明直接返回错误
    if (item === undefined) {
      return false;
    }
    // 2.2 存在则遍历item，找出对应的value
    for (let i = 0; i < item.length; i++) {
      const unit = item[i];
      const k = unit[0];
      if (key === k) {
        item.splice(i, 1);
        this.count--;
        // 3. 判断是否需要缩容，但要保证哈希表的最小容量为7
        const loadFactor = this.count / this.limit;
        if (this.limit > 7 && loadFactor < MIN_LOAD_FACTOR) {
          this.resize(this.getPrime(Math.floor(this.limit / 2)));
        }
        return unit;
      }
    }
  }

  getPrime(num) {
    while (!isPrime(num)) {
      num++;
    }
    return num;
  }

  // 扩容与压缩
  // 当装填因子(this.count/this.limit)>0.75时，进行扩容
  // 当装填因子(this.count/this.limit)<0.25时，进行缩荣
  // 当进行扩容或压缩时，需要对已有数据进行重新哈希话和再存储
  resize(newLimit) {
    const oldItems = this.items;
    // 1. 先清空旧哈希表
    this.items = [];
    this.count = 0;
    // 2. 重置哈希表容量
    this.limit = newLimit;
    // 3. 重置新哈希表
    for (let item of oldItems) {
      if (item && item.length > 0) {
        for (let unit of item) {
          this.put(unit[0], unit[1]);
        }
      }
    }
  }

  getSize() {
    return this.count;
  }
  isEmpty() {
    return this.getSize() === 0;
  }
}

export default HashTable;
